/* 单词查找树 字典树 
单词查找树的边代表 后面的字符是以这边以及前面的边构成的字符为前缀
节点代表的是以某个字符开头的全部单词的集合
*/


class node {
    constructor(base){
        this.next = new Array(base).fill(null)

    }
    // 代表某个单词结束位置
    flag = false
}
class Trie{
    constructor(){
        this.root = new node()
    }
    insert(word = '' ){
        let   p = this.node 
        /* 遍历字符串 递归插入字符  */
        for(const x  of word){
            // let ind = x.charCodeAt(0) - 'a'.charCodeAt(0) ;
            let ind = x.charCodeAt(0) - 97 ;
            if(p.next[ind] === null){ p.next[ind] = new node(26)}

            p = p.next[ind]
        }
        /* 已有这个字符串 */
        if(p.flag) {
            return false
        }
        p.flag = true ;
        return true ;
    }

    search(word){
        let  p =this.root ;
        for(const x of word){
            let ind = x.charCodeAt(0)  -97;
            if(!p.next[ind] ){ return false}
            p = p.next[ind]
            
        }
        return p.flag ;
        
    }
/* 删除要从底部开始 因此在递归的回溯阶段完成 */
    static clearTrie(root){
        if (root === null){ return}
        for( let  i =0; i < 26 ;i++){
            this.clearTrie(root.next[i])
            root = null 
            return 
        }
    }


}

/* 双数组字典树  用两个数组来表示一个字典树  */
